/*************************************************************************
 * File Name:    Best_Time_to_Buy_and_Sell_Stock_III.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/3 23:46:19
 * 
 * Description:  
 |-------------------------------------------------------------------------
 | Problem: Best Time to Buy and Sell Stock III
 | Say you have an array for which the ith element is the price of a given stock on day i.
 |
 | Design an algorithm to find the maximum profit. You may complete at most two transactions.
 | 
 | Note:
 | You may not engage in multiple transactions at the same time (ie, you must sell the
 | stock before you buy again).
 |-------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    int maxProfit(vector<int> &prices)
    {
        if (prices.size() == 0) return 0;
        
        int N = prices.size();
        vector<int> dp(N + 1, 0);
        
        int t = prices[0];
        for (int i = 1; i <= N; ++i) {
            if (prices[i - 1] <= t) {
                dp[i] = dp[i - 1];
                t = prices[i - 1];
            } else {
                dp[i] = max(dp[i - 1], prices[i - 1] - t);
            }
        }
        int ans = 0;
        
        t = prices[N - 1];
        for (int i = N - 1; i >= 1; --i) {
            if (prices[i - 1] >= t) {
                ans = max(ans, dp[i]);
                t = prices[i - 1];
            } else {
                ans = max(ans, dp[i - 1] + t - prices[i - 1]);
            }
        }
        return ans;
    }
};

